package com.lihepeng.leecode.tree.langbuladong;

import com.lihepeng.leecode.tree.TreeNode;

/**
 * 二叉搜索树
 * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
 * 针对搜索树 每一个左子树的节点都比当前节点小 右子树的节点都比当前节点大
 * 针对搜索树 每一个子树都是搜索树
 */
public class Solution230 {
    private int rank;
    private int res;
    public int kthSmallest(TreeNode root, int k) {
        travel(root,k);
        return res;
    }

    /**
     * 中序遍历
     * @param root
     * @param k
     */
    private void travel(TreeNode root, int k) {
        if (root ==null) {
            return ;
        }
        travel(root.left,k);
        rank ++;
        if (rank==k){
            res = root.val;
            return;
        }
        travel(root.right,k);
    }
}
